package com.lc.lc879;

public class Main {

}

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] f = new int[n + 1][minProfit + 1];

        for (int i = 0; i <= n; i ++) {
            f[i][0] = 1;
        }

        int len = group.length;
        int mod = (int)1e9 + 7;
        for (int i = 0; i < len; i ++) {
            for (int j = n; j >= group[i]; j --) {
                for (int k = minProfit; k >= 0; k --) {
                    f[j][k] = (f[j][k] + f[j - group[i]][Math.max(0, k - profit[i])]) % mod;
                }
            }
        }

        return f[n][minProfit];
    }
}
